package com.berchen.test;

import java.time.Duration;
import java.time.Instant;
import java.util.Arrays;

public class InsertSort {
    public static void main(String[] args) {
        int size=80;
        int[] testArr=new int[size];
        for(int i =0;i<testArr.length;i++){
            testArr[i]=(int)(Math.random()*size);
        }

        Instant start=Instant.now();
        insertSort(testArr);
        Instant end=Instant.now();
        System.out.println(Duration.between(start,end).toMillis()); //801

        System.out.println(Arrays.toString(testArr));
    }

    public static void insertSort(int[] arr) {

        for (int i = 1; i < arr.length; i++) {
            int insertIndex=i-1;
            int insertValue=arr[i];
            while (insertIndex>0&&insertValue<arr[insertIndex]){
                arr[insertIndex+1]=arr[insertIndex];
                insertIndex--;
            }
            arr[insertIndex]=insertValue;

        }
    }
}
